package com.leetCode.problem;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-04 15:14:11
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-04     张李鑫                     1.0         1.0 Version
 */
public class Problem22 {
    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * <p>
     * 有效括号组合需满足：左括号必须以正确的顺序闭合。
     */

    public static List<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<>();
        if (n == 0) {
            return list;
        }
        char[] path = new char[n << 1];
        //反括号要以0开始 如果正括号减少了 相应的反括号要增加
        process(list, 0, n, 0, path);
        return list;
    }

    private static void process(ArrayList<String> list, int index, int n,int n1, char[] path) {
        if (index == path.length) {
            list.add(String.valueOf(path));
        }
        if (n>0){
            path[index]='(';
            process(list,index+1,n-1,n1+1,path);
        }
        if (n1>0){
            path[index]=')';
            process(list,index+1,n,n1-1,path);
        }
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
}
